import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ling
 * Date: 2022-05-27
 * Time: 22:39
 */

public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap(){
        this.elem=new int[10];
    }
    public void createHeap(int[] array){
        for(int i=0;i<array.length;i++){
            elem[i]=array[i];
            usedSize++;
        }
        for(int i=(usedSize-1-1)/2;i>=0;i--){
            shiftDown(i,usedSize);
        }
    }

    /**
     * 增加元素
     * @param val
     */
    public void insertHeap(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        usedSize++;
        shifUp(usedSize-1);
    }

    /**
     * 删除堆顶元素
     * @return
     */
    public int pop(){
        if(isEmpty()){
            System.out.println("堆已空");
            return -1;
        }
        swap(0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
        return elem[usedSize];

    }
    private boolean isEmpty(){
        return usedSize==0;
    }
    private void shifUp(int child){
        int parent=(child-1)/2;
       while(child>0){
           if(elem[parent]<elem[child]){
               swap(parent,child);
               child=parent;
               parent=(child-1)/2;
           }else{
               break;
           }
       }

    }
    private boolean isFull(){
        return usedSize==elem.length;
    }
    private   void shiftDown(int root,int len){
        int parent=root;
        int child=2*parent+1;
        while(child<len){//进入这个循环说明一定有至少一个孩子
            if(child+1<len&&elem[child]<elem[child+1]){
                child++;
            }
            if(elem[parent]<elem[child]){
                swap(parent,child);
                parent=child;
                child=2*parent+1;
            }
            else{
                break;//说明此时已经是大根堆
            }

        }

    }
    private  void swap(int parent,int child){
        int tmp=elem[parent];
        elem[parent]=elem[child];
        elem[child]=tmp;
    }
    public void heapSort(){
        int len=this.usedSize-1;
        for (int i =len; i >0; i--) {
            swap(0,i);
            shiftDown(0,i);
        }

    }

}
